package primary.primary0;

import java.util.*;

public class S0047全排列II {

    class Solution3 {
        /**
         * 99， 哈哈，swap还是可以写出来的，重复值的判断思路会比较简单
         * 用swap的方式再试一次
         * 核心其实还是去重，逐个位置判断的话，就是一个值在同一个位置只能出现一次
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            // 这一行注释了从11变成99
            // Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            backTrack(0, nums, res);
            return res;
        }

        /**
         * 注意这个回溯，要一层一层搞，用i，j的话会比较麻烦，牵扯到下一组i，j是啥的决策
         */
        private void backTrack(int i, int[] nums, List<List<Integer>> res){
            if(i == nums.length - 1){
                res.add(arrayToList(nums));
                return;
            }
            Set<Integer> visited = new HashSet<>();
            for(int j = i; j < nums.length; j++){
                // 不用在意前面被换成什么样子，因为可以认为前面已经是去重的了
                // if(j != i && nums[j] == nums[i]){
                //     continue;
                // }
                // mark:上面是错的，因为判断位置i的时候，i后面的值可能被换了个遍，所以相邻的才有可能相等这种逻辑不对了，只能用set来搞
                if(visited.contains(nums[j])){
                    continue;
                }
                visited.add(nums[j]);
                swap(nums, i, j);
                backTrack(i + 1, nums, res);
                swap(nums, i, j);
            }
        }

        private List<Integer> arrayToList(int[] array){
            List<Integer> list = new ArrayList<>();
            for(int i: array){
                list.add(i);
            }
            return list;
        }

        private void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }





    /**
     * 12
     * 务必看全排列1，就上一题。这个做法就是把list换成了set，仅此而已。
     * 如果往hashSet里面塞，应该会自动去重的
     */
    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Set<List<Integer>> res = new HashSet<>();
            if(nums == null || nums.length == 0){
                return convert(res);
            }
            int totalLen = nums.length;
            List<Integer> initList = new ArrayList<>();
            initList.add(nums[0]);
            res.add(initList);

            for(int i = 1; i < totalLen; i++){
                Set<List<Integer>> resTemp = new HashSet<>();
                for(List<Integer> curList : res){
                    // List截取api要熟练
                    for(int j = 0; j <= i; j++){
                        resTemp.add(insetNumIntoList(curList, nums[i], j));
                    }
                }
                res = resTemp;
            }
            return convert(res);
        }

        public List<Integer> insetNumIntoList(List<Integer> inputList, int k, int loc){
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < inputList.size(); i++){
                if(i == loc){
                    res.add(k);
                }
                res.add(inputList.get(i));
            }
            if(loc == inputList.size()){
                res.add(k);
            }
            return res;
        }
        public List<List<Integer>> convert(Set<List<Integer>> res){
            List<List<Integer>> resList = new ArrayList<>();
            // 不太会遍历就直接冒号
            for(List<Integer> element : res){
                resList.add(element);
            }
            return resList;
        }
    }

    /**
     * 99
     * 在全排列1的基础上改的。核心还是要记住我是在逐个位置逐个位置地挑选这个位置应该放什么数字。
     * 这里是在一个个塞值，而不是在swqp了，其实都行的。
     */
    static class Solution2 {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length == 0){
                return res;
            }
            Arrays.sort(nums); // 变有序， 这个很重要
            boolean[] visited = new boolean[nums.length];
            List<Integer> curPath = new ArrayList<>();
            permuteHelp(nums, 0, visited, res, curPath);
            return res;
        }

        public void permuteHelp(int[] nums, int curLoc, boolean[] visited, List<List<Integer>> res, List<Integer> curPath){
            if(curLoc == nums.length){
                res.add(new ArrayList<Integer>(curPath));
                return;
            }
            Integer preVisited = null;
            for(int i = 0; i < nums.length; i++){
                if(!visited[i]){
                    // 核心就是，我这个函数，在调用的时候，肯定是前面curLoc - 1个位置已经确定了
                    // 然后我现在要判断curLoc位置塞什么，在塞一个位置的时候，这个位置不能塞两次一样的值。
                    // 那么如果nums变成有序的之后，就可以通过上一个值来判断了。
                    // 不能比较nums[i] 和 nums[i - 1], 因为i - 1可能是上一轮调用的时候被visited的，那么本轮就会被直接跳过
                    // 比如[1, 1, 1],我塞第二个数字的时候还一个都塞不了了。我要确认的是，本轮调用已经塞过的数字。
                    // 有序化之后比较上一个，或者搞个hashSet什么的都行。
                    if(Objects.equals(preVisited, nums[i])){
                        continue;
                    }
                    preVisited = nums[i];
                    visited[i] = true;
                    curPath.add(nums[i]);
                    permuteHelp(nums, curLoc + 1, visited, res, curPath);
                    curPath.remove(curPath.size() - 1);
                    visited[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] input = new int[]{1, 4, 2, 3, 4, 4, 5};
        System.out.println(new Solution2().permuteUnique(input));
    }
}
